
#include <vector>

using namespace std;

class Solution {
public:

    // https://leetcode.cn/problems/hanota-lcci/description/
    // 面试题 08.06. 汉诺塔问题
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
        dfs(a, b, c, a.size());
    }

    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n) 
    {
        //当n==1时，将a的盘子直接移动到c
        if (n == 1)
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }

        //借助c将a的n-1个盘子移动到b
        dfs(a, c, b, n-1);
        
        // 将a的盘子移动到c
        c.push_back(a.back());
        a.pop_back();

        //借助a将b的n-1个盘子移动到c
        dfs(b, a, c, n-1);
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    struct ListNode {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };

    // https://leetcode.cn/problems/merge-two-sorted-lists/description/
    // 21. 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
        {
            return list2;
        }
        if (list2 == nullptr)
        {
            return list1;
        }

        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else 
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }

    // https://leetcode.cn/problems/reverse-linked-list/description/
    // 206. 反转链表
    ListNode* reverseList(ListNode* head) {
        if (head==nullptr || head->next==nullptr)
        {
            return head;
        }
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }


    // https://leetcode.cn/problems/swap-nodes-in-pairs/description/
    // 24. 两两交换链表中的节点
    ListNode* swapPairs(ListNode* head) {
        if (head==nullptr || head->next==nullptr)
            return head;
        
        ListNode* tmp = swapPairs(head->next->next);
        ListNode* newhead = head->next;
        newhead->next = head;
        head->next = tmp;
        return newhead;
    }
};